#include <bits/stdc++.h>
using namespace std;

/*
1733. 需要教语言的最少人数
已解答
中等
相关标签
premium lock icon
相关企业
提示
在一个由 m 个用户组成的社交网络里，我们获取到一些用户之间的好友关系。两个用户之间可以相互沟通的条件是他们都掌握同一门语言。

给你一个整数 n ，数组 languages 和数组 friendships ，它们的含义如下：

总共有 n 种语言，编号从 1 到 n 。
languages[i] 是第 i 位用户掌握的语言集合。
friendships[i] = [u​​​​​​i​​​, v​​​​​​i] 表示 u​​​​​​​​​​​i​​​​​ 和 vi 为好友关系。
你可以选择 一门 语言并教会一些用户，使得所有好友之间都可以相互沟通。请返回你 最少 需要教会多少名用户。

请注意，好友关系没有传递性，也就是说如果 x 和 y 是好友，且 y 和 z 是好友， x 和 z 不一定是好友。
 

示例 1：

输入：n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]]
输出：1
解释：你可以选择教用户 1 第二门语言，也可以选择教用户 2 第一门语言。
示例 2：

输入：n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]]
输出：2
解释：教用户 1 和用户 3 第三门语言，需要教 2 名用户。
 

提示：

2 <= n <= 500
languages.length == m
1 <= m <= 500
1 <= languages[i].length <= n
1 <= languages[i][j] <= n
1 <= u​​​​​​i < v​​​​​​i <= languages.length
1 <= friendships.length <= 500
所有的好友关系 (u​​​​​i, v​​​​​​i) 都是唯一的。
languages[i] 中包含的值互不相同。
*/

// 法一
class Solution {
public:
    int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {
        int m = languages.size();
        // 每个语言进哈希映射
        vector<unordered_set<int>>  userLanguage;
        for (auto& lan : languages)     userLanguage.emplace_back(lan.begin(), lan.end());

        // set去重 
        unordered_set<int> problemUsers;
        for (auto& fs : friendships) {
            // 0-base数组
            int u = fs[0] - 1, v = fs[1] - 1;

            // check same lan
            bool hasSame = false;
            // 遍历来看 然后标志量判断
            for (int lan : userLanguage[u]) {
                if (userLanguage[v].count(lan)) {
                    hasSame = true;
                    break;
                }
            }

            if (!hasSame) {
                // 问题数组记录一下
                problemUsers.insert(u);
                problemUsers.insert(v);
            }
        }
        // 没有存在沟通问题的好友对 无需教学
        if (problemUsers.empty())   return 0;

        // 找需要的用户数量 min val
        int minTeach = INT_MAX;
        for (int i = 1; i <= n; i++) {
            int needTeach = 0;
            for (int user : problemUsers) {
                // 没掌握就教学
                if (!userLanguage[user].count(i))       needTeach++;
            }
            minTeach = min(minTeach, needTeach);
        }
        return minTeach;
    }
};

// 法二
class Solution {
public:
    int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {
        int m = languages.size(); // m为用户总数（0-based索引）
        // learned[i][x]：标记用户i是否掌握语言x（空间优化用int8_t）
        vector learned(m, vector<int8_t>(n + 1));
        for (int i = 0; i < m; i++) {
            for (int x : languages[i]) {
                learned[i][x] = true;
            }
        }

        int total = 0; // 统计所有存在沟通问题的用户总数（去重后）
        vector<int8_t> vis(m); // 标记用户是否已被纳入统计（避免重复计算）
        vector<int> cnt(n + 1); // cnt[x]：统计存在沟通问题的用户中，掌握语言x的人数

        // 处理存在沟通问题的用户：将其纳入统计，更新总人数和各语言掌握数
        auto add = [&](int u) -> void {
            if (vis[u]) { // 已统计过的用户跳过
                return;
            }
            vis[u] = true; // 标记为已统计
            total++; // 总问题用户数+1
            // 该用户掌握的每种语言，对应计数+1
            for (int x : languages[u]) {
                cnt[x]++;
            }
        };

        // 遍历所有好友对，筛选出存在沟通问题的用户
        for (auto& f : friendships) {
            int u = f[0] - 1, v = f[1] - 1; // 转换为0-based索引
            bool ok = false; // 标记该好友对是否能正常沟通
            // 检查u和v是否有共同语言
            for (int x : languages[u]) {
                if (learned[v][x]) { // v也掌握语言x，可沟通
                    ok = true;
                    break;
                }
            }
            if (!ok) { // 无共同语言，属于需要处理的问题好友对
                add(u); // 将u纳入问题用户统计
                add(v); // 将v纳入问题用户统计
            }
        }

        // 最少教学人数 = 问题用户总数 - 掌握人数最多的语言的用户数
        // （选择该语言时，已有cnt[x]人会，只需教剩下的人）
        return total - ranges::max(cnt);
    }
};